Constraint systems are difficult to debug because they are declarative in nature, which means there is no execution process as for imperative code. Instead, constraints are evaluated by an algorithm which is obscure to the user. Examples of such constraint systems may be found in PCT Application Nos. PCT/IL01/01011 and PCT/IL01/00508, and U.S. Pat. No. 6,219,809, all of which are hereby incorporated by reference as if fully set forth herein.
Constraint based programs include generation entities which include data structures and variables whose values are determined according to constraints. These are referred to as fields in this application. Generation entities include constraints that determine the relationships between fields and other fields, or between fields and constants. Generation entities can be defined by the user input, as well as inferred by some computation which creates temporary fields for instance.
Generation entities may relate to each other, for example two fields may be related through a common constraint. Sometimes the user needs to focus on the transitive closure of some generation entity rather that the entity itself. Such transitive closure is the group of all entities that relate to other members of the group.
In a constraint based program, generateable fields are assigned by a constraint resolution process. A constraint resolution process involves a sequence of generation decisions, which are either generation events or field ordering. Generation events relate to generation entities, such as fields and constraints, and represent a change in the status or the value of the generation entity. For example, a field being assigned a specific value is a generation event related to that field. A constraint being used to reduce the permissible values of a field is a generation event related to that constraint. Field ordering represents the sequential order in which fields are being considered for generation.
Generation decisions are dynamic entities that are created as part of the constraint resolution process. Generation events are ordered according to the sequence of execution. Generation may be caused by some earlier events and may be the reason for some later events. Such causal chains are represented as paths connecting related events according to their sequential order.
Generation decisions are collected during constraint resolution and presented at a later point in time when the user wishes to debug the generation process. The generation process is known to involve at least two stages, namely static analysis and runtime, as described for example with regard to U.S. Pat. No. 6,182,258. It is advantageous to collect generation decisions during these phases, so that problems uncovered early in the process can be debugged as well. For example, static analysis may conclude that a contradiction exists within the set of constraints presented. The generation debugger can be used to view the generation decisions that led to that conclusion even though no runtime generation took place.
The background art focuses on presenting the state of the generation objects at various stages of constraint resolution, but lacks a systematic representation of the generation decisions.
The following reference discusses visualization of constraint based systems:
Analysis and Visualization Tools for Constraint Programming: Constraint Debugging (Lecture Notes in Computer Science number 1870, January 2001, by Pierre Deransart (Editor), Manuel V. Hermenegildo (Editor), Maluszynski, Springer Verlag; ISBN: 3540411372, which is hereby incorporated by reference as if fully set forth herein.
The current invention differs from prior art in two major aspects. The current invention is capable of representing complex constraints systems such as the constraints disclosed in U.S. Pat. No. 6,182,258. Such complex constraints systems may include:                1. a dynamically changing set of constraints based on the state of the constraint resolution process,        2. a hierarchical set of constraints applied to complex data structures and lists, and        3. fields that are under-constrained which are assigned a random value from the set of permissible values computed.        
The other novel approach of this invention, compared to prior art is related to the representation of the constraint resolution process. Prior art teaches a static view of the set of applicable constraints, where a resolution process may be viewed as a series of such static snapshots. Such a representation omits crucial information about the reason for the transformation from one snapshot to the next.
Another approach common in the art is supplying some debug information about the constraint resolution engine, which is typically a program written in some logic programming language (Prolog for example). Such information may include the procedures that where called during resolution, contradictions and backtracking information. This information is typically presented during execution and may be used to intervene with the execution of the resolution engine for the purpose of debugging. Making use of this information requires intimate understanding of the constraint resolution procedure, which is exceedingly complex.
In contrast the current invention collects information during the execution of the constraint resolution engine, but presents that information after the execution in a semantic framework that is much simpler than the actual implementation of the constraint resolution engine. The resolution process is conceptualized using generation events and their relationship to changes that occur on field values and constraint status. Generation events present sequential relationships that provide cause and effect analysis of the constraint resolution process without requiring any knowledge of the implementation of the constraint resolution engine.